// https://leetcode.cn/problems/divide-two-integers/
// Created by ade on 2022/8/17.
// 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
//
// 返回被除数 dividend 除以除数 divisor 得到的商。
//
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

// 被除数和除数均为 32 位有符号整数。
// 除数不为 0。
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
#include <iostream>


using namespace std;

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 1) return dividend;
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;// 溢出情况处理
        if (dividend == 0) return 0;// 被除数为0情况处理
        if (divisor == INT_MIN) {
            // 被除数的特殊处理，否则转换为正数会溢出
            if (dividend == INT_MIN) return 1;
            return 0;
        }
        // 转换成正数处理
        int over = 0; // 溢出标志
        int flag = 1;
        if (dividend < 0) {
            if (dividend == INT_MIN) {
                dividend = INT_MAX;
                over = 1;
            } else {
                dividend = -dividend;
            }
            flag = -flag;
        }
        if (divisor < 0) {
            divisor = -divisor;
            flag = -flag;
        }
        if (dividend < divisor) return 0;// 被除数为0情况处理
        int res = 0, step = 1;
        int d = divisor;
        while (1) {
            dividend -= d;
            res += step;
            step <<= 1;
            d <<= 1;
            if (dividend == 0 || dividend > 0 && dividend < divisor) break;
            if (dividend < 0) {
                dividend += (d >> 1);
                d = divisor;
                step = 1;
            } else if (dividend < d) {
                d = divisor;
                step = 1;
            }
        }
        if (over && (dividend + over) == divisor) res++;

        if (flag == -1) res = -res;
        return res;
    }
};

int main() {
    Solution so;
    cout << so.divide(INT_MAX, 2) << endl;
    return 0;
}